#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
#include<map>


using namespace std;
enum colour
{
	Red,
	Black
};
template<class k,class v>
class RBNode
{
public:
	RBNode(const pair<k,v>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		,_kv(kv)
		{}

public:
	pair<k, v> _kv;
	RBNode<k, v>* _left;
	RBNode<k, v>* _right;
	RBNode<k, v>* _parent;
	colour _col;
};
template<class k,class v>
class RBTree
{
	typedef RBNode<k,v> Node;
public:
	bool Insert(const pair<k, v>& kv)
	{
		Node* cur = _root;	Node* parent = nullptr;
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = Black;
			return true;
		}
		while (cur)
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return false;
		}
		cur = new Node(kv);
		cur->_col = Red;
		if (kv.first < parent->_kv.first)
			parent->_left = cur;
		else
			parent->_right = cur;
		cur->_parent = parent;

		while (parent && parent->_col == Red)
		{
			Node* grandfather = parent->_parent;
			assert(grandfather);
			assert(grandfather->_col == Black);
			Node* uncle = nullptr;
			if (grandfather->_left == parent)
				uncle = grandfather->_right;
			else
				uncle = grandfather->_left;
			if (uncle && uncle->_col == Red)
			{
				parent->_col = Black;
				uncle->_col = Black;
				grandfather->_col = Red;
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				if (parent->_left == cur && grandfather->_left == parent)
				{
					RoateR(grandfather);
					grandfather->_col = Red;
					parent->_col = Black;
					break;
				}
				else if (parent->_right == cur && grandfather->_right == parent)
				{
					RoateL(grandfather);
					grandfather->_col = Red;
					parent->_col = Black;
					break;
				}
				else if (parent->_left == cur && grandfather->_right == parent)
				{
					RoateR(parent);
					RoateL(grandfather);
					grandfather->_col = Red;
					cur->_col = Black;
					break;
				}
				else
				{
					RoateL(parent);
					RoateR(grandfather);
					grandfather->_col = Red;
					cur->_col = Black;
					break;
				}
			}
		}
		_root->_col = Black;
		return true;
	}
	void InOrder()
	{
		_InOrder(_root);
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first<<" ";
		_InOrder(root->_right);
	}
	void RoateL(Node* parent)
	{
		Node* subr = parent->_right;
		Node* subrl = subr->_left;
		parent->_right = subrl;
		if (subrl)
			subrl->_parent = parent;
		Node* ppnode = parent->_parent;
		subr->_left = parent;
		parent->_parent = subr;
		if (ppnode)
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subr;
				subr->_parent = ppnode;
			}
			else
			{
				ppnode->_right = subr;
				subr->_parent = ppnode;
			}
		}
		else
		{
			_root = subr;
			subr->_parent = nullptr;
		}
	}
	void RoateR(Node* parent)
	{
		Node* subl = parent->_left;
		Node* sublr = subl->_right;
		parent->_left = sublr;
		if (sublr)
			sublr->_parent = parent;
		Node* ppnode = parent->_parent;
		subl->_right = parent;
		parent->_parent = subl;
		if (ppnode)
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subl;
				subl->_parent = ppnode;
			}
			else
			{
				ppnode->_right = subl;
				subl->_parent = ppnode;
			}
		}
		else
		{
			_root = subl;
			subl->_parent = nullptr;
		}
	}
	Node* _root=nullptr;

};